package 动态规划.样本对应模型;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/3/8 16:19
 */
public class leetcode718最长重复子数组 {
    /*
     通过 该题, 与 最长 公共子序列 ,去比较
     然后思考一下 这两种 题型的一个区别!
    ** 这个题 与最长 公共子序列 的一些 区别 **

    该题的  子数组要求连续, 而子序列 并未要求连续.

    注意一下  这两个题, 对应的函数的 含义 不一样!
    最长公共子序列: f(i , j)
    最长重复子数组: f(i, j)  这两个 抽象的 有点 不太好 解释!

     */


    public int recursion(int i,int j,int nums1[],int nums2[]){
        if(i == nums1.length || j == nums2.length){
            return 0;
        }
        int ans = 0;
        if(nums1[i] == nums2[j]){
            ans = recursion(i + 1,j + 1,nums1,nums2) + 1;
        }
        return ans;
    }

    /*
    可以 使用 滚动数组 优化 一下: (如果有需要的 话 知道 怎么 做就行了 (如果 某些 题 卡 空间的 话!))
    https://blog.csdn.net/m0_46427179/article/details/107419492
    也可以 根据 卡尔 的  网址, 去优化 一下:

    ==
     这就 A 了
     */

    public int dp(int nums1[],int nums2[]){
        int dp[][] = new int[nums1.length + 1][nums2.length + 1];
        int max = 0;
        for(int i = nums1.length - 1;i >= 0;i--){
            for(int j = nums2.length - 1;j >= 0;j--){
                if(nums1[i] == nums2[j]){
                    dp[i][j] = dp[i + 1][j + 1] + 1;
                }
                max = Math.max(max,dp[i][j]);
            }
        }
        return max;
    }

}
